package leetcode.year2021.month12;

import leetcode.utils.ListNode;

//23. 合并K个升序链表
public class _05_1MergeKLists23 {
  /**
   * 思路： 使用归并的思路，但是需要注意下标的定义，不能越界
   * 还可以用优先队列的思路解题（未看）
   * @param lists
   * @return
   */
  public ListNode mergeKLists(ListNode[] lists) {
    int length = lists.length;
    if (length == 0){
      return null;
    }
    return mergeKListsByDfs(lists,0,length-1);
  }

  private ListNode mergeKListsByDfs(ListNode[] lists, int left, int right) {
    int currLength = right - left + 1;

    if (currLength == 1){
      return lists[left];
    } else {
      ListNode leftAns = mergeKListsByDfs(lists,left,left+(currLength-1)/2);
      ListNode rightAns = mergeKListsByDfs(lists,left+(currLength-1)/2+1,right);
      return mergeTwoNodeList(leftAns,rightAns);
    }

  }

  public ListNode mergeTwoNodeList(ListNode l1, ListNode l2){
    ListNode dummy = new ListNode(0);
    ListNode prev = dummy;
    while (l1 != null || l2 != null){
      if (l1 == null){
        prev.next = l2;
        break;
      }
      if (l2 == null){
        prev.next = l1;
        break;
      }
      if (l1.val > l2.val){
        prev.next = l2;
        prev = prev.next;
        l2 = l2.next;
        prev.next = null;
      } else {
        prev.next = l1;
        prev = prev.next;
        l1 = l1.next;
        prev.next = null;
      }
    }

    return dummy.next;
  }

  /**
   * 23. 合并K个升序链表
   * 给你一个链表数组，每个链表都已经按升序排列。
   *
   * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
   *
   *
   *
   * 示例 1：
   *
   * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
   * 输出：[1,1,2,3,4,4,5,6]
   * 解释：链表数组如下：
   * [
   *   1->4->5,
   *   1->3->4,
   *   2->6
   * ]
   * 将它们合并到一个有序链表中得到。
   * 1->1->2->3->4->4->5->6
   * 示例 2：
   *
   * 输入：lists = []
   * 输出：[]
   * 示例 3：
   *
   * 输入：lists = [[]]
   * 输出：[]
   *
   *
   * 提示：
   *
   * k == lists.length
   * 0 <= k <= 10^4
   * 0 <= lists[i].length <= 500
   * -10^4 <= lists[i][j] <= 10^4
   * lists[i] 按 升序 排列
   * lists[i].length 的总和不超过 10^4
   */
}
